Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:

S = "rabbbit", T = "rabbit"

Return 3.

Solution:

  1. public class Solution {
  2.   public int numDistinct(String s, String t) {
  3.     int n = s.length(), m = t.length();
  5.     // dp(i, j) represents the count of S(1...i) and T(1...j)
  6.     int[][] dp = new int[n + 1][m + 1];
  8.     for (int i = 0; i <= n; i++)
  9.       dp[i][0] = 1;
  11.     for (int i = 1; i <= n; i++) {
  12.       for (int j = 1; j <= m; j++) {
  13.         if (s.charAt(i - 1) == t.charAt(j - 1)) {
  14.           dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  15.         } else {
  16.           dp[i][j] = dp[i - 1][j];
  17.         }
  18.       }
  19.     }
  21.     return dp[n][m];
  22.   }
  23. }